home *** CD-ROM | disk | FTP | other *** search
/ EuroCD 3 / EuroCD 3.iso / Programming / Python-1.4 / Demo / scripts / fact.py < prev    next >
Encoding:
Python Source  |  1998-06-24  |  922 b   |  49 lines
  1. #! /usr/local/bin/python
  2.  
  3. # Factorize numbers.
  4. # The algorithm is not efficient, but easy to understand.
  5. # If there are large factors, it will take forever to find them,
  6. # because we try all odd numbers between 3 and sqrt(n)...
  7.  
  8. import sys
  9. from math import sqrt
  10.  
  11. error = 'fact.error'        # exception
  12.  
  13. def fact(n):
  14.     if n < 1: raise error    # fact() argument should be >= 1
  15.     if n == 1: return []    # special case
  16.     res = []
  17.     # Treat even factors special, so we can use i = i+2 later
  18.     while n%2 == 0:
  19.         res.append(2)
  20.         n = n/2
  21.     # Try odd numbers up to sqrt(n)
  22.     limit = sqrt(float(n+1))
  23.     i = 3
  24.     while i <= limit:
  25.         if n%i == 0:
  26.             res.append(i)
  27.             n = n/i
  28.             limit = sqrt(n+1)
  29.         else:
  30.             i = i+2
  31.     if n != 1:
  32.         res.append(n)
  33.     return res
  34.  
  35. def main():
  36.     if len(sys.argv) > 1:
  37.         for arg in sys.argv[1:]:
  38.             n = eval(arg)
  39.             print n, fact(n)
  40.     else:
  41.         try:
  42.             while 1:
  43.                 n = input()
  44.                 print n, fact(n)
  45.         except EOFError:
  46.             pass
  47.  
  48. main()
  49.